<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>最长公共子串和子序列</title>
    </head>
    <body></body>
    <!-- 实现 -->
    <script src="./js/最长公共子串和子序列-1.js"></script>
    <!-- 优化 -->
    <!-- <script src="./js/最长公共子串和子序列-2.js"></script> -->
    <script>
        // 假如有两个字符串，s1="people"和s2="eplm"，我们要求他俩最长的公共子串。
        // 我们一眼就能看出他们的最长公共子串是"pl"，长度是2。但如果字符串特别长的话就不容易那么观察了。

        /**
         * 我们用一个二维数组dp[i][j]表示第一个字符串前i个字符和第二个字符串前j个字符 组成的最长公共字符串的长度。那么我们在计算dp[i][j]的时候，
         * 我们首先要判断s1.charAt(i)是否等于s2.charAt(j)，如果不相等，说明当前字符无法构成公共子串，所以dp[i][j]=0。如果相等，说
         * 明可以构成公共子串，我们还要加上他们前一个字符构成的最长公共子串长度，也就是dp[i-1][j-1]。所以我们很容易找到递推公式
         *
         *  if(s1.charAt(i) === s2.charAt(j)) {
         *      dp[i][j] = dp[i-1][j-1] + 1;
         *  } else {
         *      dp[i][j] = 0;
         *  }
         *
         * */

        const str1 = "people";
        const str2 = "eplm";
        console.log(maxLong(str1, str2));
    </script>
</html>
